Game theoretic controller synthesis for multi-robot motion planning Part I : Trajectory based algorithms

摘要

We consider a class of multi-robot motion planning problems where each robotis associated with multiple objectives and decoupled task specifications. Theproblems are formulated as an open-loop non-cooperative differential game. Adistributed anytime algorithm is proposed to compute a Nash equilibrium of thegame. The following properties are proven: (i) the algorithm asymptoticallyconverges to the set of Nash equilibrium; (ii) for scalar cost functionals, theprice of stability equals one; (iii) for the worst case, the computationalcomplexity and communication cost are linear in the robot number.